HW-3

Damanpreet Singh (damanprs)

Q1A1 - 8 Point

For this question, to calculate the fundamental matrix using 8-point algorithm, the following steps were followed:

• The correspondences are loaded up
• The correspondences are normalized using the following approach, which involves zero-centering and enforcing unit variance. This has been coded as the $\textit{normalize_pts()}$ function in the code
• The normalized correspoondences are then projected into $\mathbb{P}^2$ space, by appending 1 at the end
• The correspondences are then used to calculate the F matrix
• The F matrix is unnormalized, by using $F_{unnorm} = T_2^T F_{norm} T_1$
• The correspondences are stacked up into a matrix $A$ and a system of linear equations as $A\vec{f}=0$ is developed for estimating the fundamental matrix. Here $\vec{f}$ is the flattened fundamnetal matrix
• The A matrix is formed using a pair of correspondences as shown below
• Here the dashed variables belong the second image and non-dashed belong tho the first image
• All the correspondences are then staked up in the $A$ matrix
• $\vec{f}$ is calculated using Singular Value Decomposition(SVD) of $A$ matrix, using $\textit{np.linalg.svd()}$
• $\vec{f}$ is the last singular vector of the SVD of A
• $\vec{f}$ is then reshaped to obtain the fundamental matrix $F$
• To enforce singularity constraint on $F$, its SVD is computed and the last singular value is forced to zero
• This yields the final fundamental matrix
• The estimated matrices have been shown below

$F_{teddy} = \begin{bmatrix} 5.91433056e-08 & -2.12678213e-08 & 3.10190612e-04\\ -2.30657434e-07 & -1.45515544e-07 & -1.84284386e-03\\ -8.60754012e-04 & 2.10624262e-03 & 4.64649423e-01 \end{bmatrix}$

$F_{chair} = \begin{bmatrix} -1.88584882e-08 & -3.06155021e-07 & 1.22762898e-04\\ 4.54529423e-07 & -4.40348965e-08 & -2.63156531e-03\\ 5.53598191e-06 & 2.67574197e-03 & -1.50048184e-01 \end{bmatrix}$

• The results can be seen below

Q1A2 - Essential Matrix

For calculating the Essential matrix ($E$), the following steps were followed:

• The intrinsics for both the cases were loaded up
• $E$ was calculated as $E = K_2^T F K_1$, where $K_1$ and $K_2$ are the intrinsic matrices for the first and second image respectively
• The computed essential matrices can be seen below

$E_{teddy} = \begin{bmatrix} 0.06272501 & -0.0225558 & 7 0.37052478\\ -0.24462599 & -0.15432793 & -2.16728799\\ -0.90077148 & 2.105036 & -0.01168117 \end{bmatrix}$

$E_{chair} = \begin{bmatrix} -0.01698553 & -0.27574879 & -0.16417522\\ 0.40938717 & -0.03966151 & -2.40478211\\ 0.40921935 & 2.41569513 & -0.06745823 \end{bmatrix}$

Q1B - 7 Point

The steps followed for computing the fundamnetal matrix using 7 point algorithm as as follows:

• The 7 point correpondences are loaded up
• The points are then normalized and projected into $\mathbb{P}^2$ space in a similar way as Q1
• Similar to Q1, the points are stacked up in a linear system of equations as $Af=0$
• In this, we get the last two singular vectors of the SVD of $A$ and the fundamental matrix is a linear combination of these, given as $F = \lambda F_1 + (1-\lambda)F_2$
• To compute $\lambda$, we need to solve the cubic equation arising from $det(F) = 0$
• The cubic equation can be assumed as $A\lambda^3 +B\lambda^2 + C\lambda + D$
• The coefficients are calculated as follows

$F = \lambda F_1 + (1-\lambda)F_2 \Rightarrow F = \lambda(F_1 - F_2) + F_2$
Let $F_1 - F_2 = F_{coeff}$ and $F_2 = F_{const} \Rightarrow F = \lambda F_{coeff} + F_{const}$

Let $F_{coeff} = \begin{bmatrix} \vec{a_1} & \vec{a_2} & \vec{a_3} \end{bmatrix}$ and $F_{const} = \begin{bmatrix} \vec{b_1} & \vec{b_2} & \vec{b_3} \end{bmatrix}$

Now, the coefficients for the cubic equation in lambda are given as

$A = det(F_{coeff})$

$B = det\begin{pmatrix}\vec{a_1} & \vec{a_2} & \vec{b_3} \end{pmatrix} + det\begin{pmatrix}\vec{a_1} & \vec{b_2} & \vec{a_3} \end{pmatrix} + det\begin{pmatrix}\vec{b_1} & \vec{a_2} & \vec{a_3} \end{pmatrix} $

$C = det\begin{pmatrix}\vec{a_1} & \vec{b_2} & \vec{b_3} \end{pmatrix} + det\begin{pmatrix}\vec{b_1} & \vec{a_2} & \vec{b_3} \end{pmatrix} + det\begin{pmatrix}\vec{b_1} & \vec{b_2} & \vec{a_3} \end{pmatrix} $

$D = det(F_{const})$

• The roots for this cubic equation are calculated by passing the tuple $(A,B,C,D)$ in $\textit{numpy.roots()}$
• There can be two feasible ouputs from this i.e 1 real , 3 real roots
• In case of 1 real root, we have a single answer
• In case of 3 real roots, calculate the the three possible fundamental matrices as $F1 = \lambda_1 F_{coeff} +F_{const}$, $F2 = \lambda_2 F_{coeff} +F_{const}$ and $F3 = \lambda_3 F_{coeff} +F_{const}$
  • Choose the $F$ which gives the lowest value of $x_2^T F x_1$, for all points
• For our problem, both the case of "toybus" and "toytrain" gave a single real root
• The Fundamental matrices came out to be

$F_{toybus} = \begin{bmatrix} -1.74903938e-06 & 4.22226422e-05 & -6.82374875e-02\\ -6.26047416e-06 & -1.20299872e-04 & 2.34842386e-01\\ 8.17490954e-02 & 1.26366146e-01 & -7.08454540e+01 \end{bmatrix}$

$F_{toytrain} = \begin{bmatrix} 3.66141915e-06 & -8.86148804e-05 & 4.84974472e-02\\ 2.62915797e-05 & -2.24421533e-05 & 7.64438496e-02\\ -1.51307953e-02 & -2.30522700e-02 & -2.80681850e+01 \end{bmatrix}$

• The visualization of epipolar lines can be seen below

Toybus

Toytrain

Q2 - RANSAC with 8 point

The steps followed for 8 point RANSAC are listed below:

• At each iteration
  • The $F$ matrix is calculated using the same function as Q1A1, using 8 random correspondences
  • The error is calculated as $x_2^T F x_1$, using the all the correspondences other than the ones used to calculate $F$
  • Goal is to minimize this to 0
  • Each error is checked against the error threshold and inliers are stacked up
  • If number of inliers are greater than the last greatest inliers, best inliers are updated
  • At the end of all the iterations, the F matrix is calculated again, using these best inliers

The graph and epipolar lines for 8 point can be seen below

Toybus

$F_{toybus\_RANSAC8} = \begin{bmatrix} -5.07668571e-07 & 2.50841490e-06 & -1.33747166e-03\\ -3.10150685e-06 & -5.28552738e-07 & -5.94904219e-03\\ 1.07023298e-03 & 7.69400029e-03 & 1.00000000e+00 \end{bmatrix}$

Toytrain

$F_{toytrain\_RANSAC8} = \begin{bmatrix} -8.08954167e-06 & 2.83462187e-06 & -1.83412673e-02\\ -1.51324647e-05 & 4.99666641e-06 & -3.39806944e-02\\ 2.30915777e-02 & 3.96680542e-02 & 1.00000000e+00 \end{bmatrix}$

RANSAC with 7 point

The steps are similar to RANSAC with 8 point, with 1 difference

• For 7 point, we can get either 1 real root or 3 real roots
• If we get 1 real root, algorithm is completely similar to RANSAC 8 point
• If we get 3 real roots, the F matrix is calculated for all the 3 matrices and the one giving maximum inliers is chosen

The graphs and epipolar line visulaization are shown below

Toybus

$F_{toybus\_RANSAC7} = \begin{bmatrix}-6.43780977e-08 & 4.11962066e-07 & 1.68251299e-04\\ -5.87584608e-07 & 1.05709745e-07 & -4.09276129e-03\\ -7.77023056e-04 & 4.30303151e-03 & 1.00000000e+00 \end{bmatrix}$

Toytrain

$F_{toytrain\_RANSAC7} = \begin{bmatrix}-4.22305732e-06 & -6.37069658e-06 & -6.09514665e-03\\ -4.07259422e-06 & 5.58902765e-06 & -2.25625052e-02\\ 9.78975517e-03 & 2.40012054e-02 & 1.00000000e+00 \end{bmatrix}$

Q3 - Triangulation

For this question, the steps followed are as follows:

• The camera matrices and the 2D points are loaded up

• For each point, the 3D point is estimated, by solving a system of linear equations $AX=0$, where $X$ is the 3D point in $\mathbb{P}^3$ and A is the matrix as shown below

• It is to be noted, that each point correspondence gives only 4 constraints, so size of $A$ is $4 \times 4$

• This equation is solved using SVD, for each 2D point pair
• The obtained 3D point matriox $X$, is then projected using matplotlib scatter plot

The point cloud can be seen below (green background is used for contrast)

Q4 - Bundle Adjustment

For bundle adjustment, the following steps are used:

• The 2D points and noisy camera matrices are loaded up
• Initial triangulation is done
• The $\textit{scipy.optimize.least_squares()}$ function with the 'dogleg' method is then used for the non linear optimization
• The x0 varible for this is a flattened vector of $[P1 , P2 , X]$, here $P1,P2$ are the initial noisy camera matrices and $X$ is the flattened matrix of the noisy 3D points

• The residual function is defined to return the reprojection error for each pixel in both the images as shown below

• The scipy.optimize.least_squares() returns the optimized camera matrices and 3D points

• These optimized camera matrices are used to triangulate the 3D points accurately

The camera matrices and triangulations before and after BA can be seen below

$P1_{final} = \begin{bmatrix} 1.84416264e+03 & 1.10451211e+02 & -1.79053798e+03 & 2.56000492e+03\\ 3.35919869e+02 & 2.50819410e+03 & 4.64117828e+02 & 2.55995702e+03\\ 9.24442013e-03 & -3.83348980e+00 & 1.60913861e+00 & 1.02039353e+01 \end{bmatrix}$

$P2_{final} = \begin{bmatrix} 2.52397269e+03 & 4.85406968e+00 & -5.38194204e+02 & 2.55671311e+03\\ 8.82947738e+01 & 2.54982532e+03 & 2.82638960e+02 & 2.56708315e+03\\ -4.52630307e-01 & -3.83931532e+00 & 1.95133707e+00 & 1.02436862e+01 \end{bmatrix}$

Before Bundle Adjustment

After Bundle Adjustment

Q5 - Fundamental matrix estimation on own images

• Image pairs were taken from the Co3D dataset
• As was given in the writeup, SIFT feature extraction was used
• For matching the features, Brute-Force Matcher from opencv was used
• Matches were filtered to remove outliers, using the ratio test as shown $\href{https://docs.opencv.org/4.x/dc/dc3/tutorial_py_matcher.html}{here}$
• These matches are then used with the RANSAC 8-point function explained in Q2

The input images with the matches and epipolar lines can be seen below

Car 1

Image 1

Image 2

Matches

Epipolar lines

Car 2

Image 1

Image 2

Matches

Epipolar Lines

Late Days